package com.zdp.leetcode;

import com.zdp.util.ListNode;

/*
* 题目描述：
*将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 合并两个有序链表 {

    //使用新建一个链表的方法
    //有序链表的合并   其实任何有序的合并  我感觉都是 先比较 然后插入  只是使用的数据结构的不同，插入的方式也会有所不同
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode rptr = result;
        ListNode p1 = l1;
        ListNode p2 = l2;
        while(p1!=null&&p2!=null){
            ListNode r = new ListNode();
            if(p1.val<=p2.val){
                r.val = p1.val;
                p1 = p1.next;
            }else{
                r.val = p2.val;
                p2 = p2.next;
            }
            rptr.next = r;
            rptr = rptr.next;
        }
        if(p1==null){
            while(p2!=null){
                ListNode r = new ListNode(p2.val);
                rptr.next = r;
                rptr = rptr.next;
                p2 = p2.next;
            }
        }else{
            while(p1!=null){
                ListNode r = new ListNode(p1.val);
                rptr.next = r;
                rptr = rptr.next;
                p1 = p1.next;
            }
        }
        rptr.next = null;
        return result.next;
    }

    //直接在原来的链表上改动 使用递归
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if(l1==null&&l2==null){ //注意边界条件  1->2->4 1->3->4
            return l1;
        }
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;

        ListNode p ; //p记录的是当前最小的，p.next -> 应该链向下一个当前最小 ，所以return p
        if(l1.val<l2.val){
            //小于就合并
            p = l1; //
            p.next = mergeTwoLists1(l1.next,l2);
        }else{
            p = l2;
            p.next = mergeTwoLists1(l1,l2.next);
        }
        return p;
    }
    //使用迭代
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode phead = head;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                phead.next = l1;
                l1 = l1.next;
            }else{
                phead.next = l2;
                l2 = l2.next;
            }
            phead = phead.next;
        }
        phead.next = l1==null?l2:l1;
        return head.next;
    }
}

